package kdtree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import primatives.PointND;

import triangulation.DelaunayMapping;
import util.GeoVertex;
import util.PointCloudReader;

/*
 * Special KD-tree for GeoVertices 
 * 
 */

public class KDTree
{
	private class XCompare implements Comparator<GeoVertex>
	{
		@Override
		public int compare(GeoVertex v, GeoVertex u)
		{
			if (v.x() > u.x()) return 1;
			else if (v.x() < u.x()) return -1;
			return 0;
		}
	}
	
	private class YCompare implements Comparator<GeoVertex>
	{
		@Override
		public int compare(GeoVertex v, GeoVertex u)
		{
			if (v.y() > u.y()) return 1;
			else if (v.y() < u.y()) return -1;
			return 0;
		}
	}
	
	private class ZCompare implements Comparator<GeoVertex>
	{
		@Override
		public int compare(GeoVertex v, GeoVertex u)
		{
			if (v.y() > u.y()) return 1;
			else if (v.y() < u.y()) return -1;
			return 0;
		}
	}
	
	private int dim = 3; // use just 3d coords for now 
	
	public Node root;
	private XCompare x_dim_comp;
	private YCompare y_dim_comp;
	private ZCompare z_dim_comp;
	
	public KDTree(ArrayList<GeoVertex> list)
	{
		x_dim_comp = new XCompare();
		y_dim_comp = new YCompare();
		z_dim_comp = new ZCompare();
		
		build(list);
	}

	
	/*
	 * Traverse the tree from the root and place the element in the right place...
	 */
	public void add(GeoVertex gv)
	{
		
	}
	
	public void build(ArrayList<GeoVertex> list)
	{
		root = build(list, 0);
	}
	
	
	/*
	 * Sort the list by x, then y then z
	 */
	private Node build(List<GeoVertex> list, int depth)
	{
		if (list.size() == 0) return null;
		if (list.size() == 1)
		{
			Node t = new Node();
			t.data = list.get(0);
			return t;
		}
		
		// select axis based on depth
		int axis = depth % dim;
		
		if (axis == 0) Collections.sort(list, x_dim_comp);
		if (axis == 1) Collections.sort(list, y_dim_comp);
		if (axis == 2) Collections.sort(list, z_dim_comp);

		// select median by axis from list
		int median = (list.size() / 2);
		
		Node t = new Node();
		t.data = list.get(median);
		
		List<GeoVertex> left_list = list.subList(0, median);
		List<GeoVertex> right_list = list.subList(median + 1, list.size() - 1);
		
		t.left = build(left_list, depth + 1);
		t.right = build(right_list, depth + 1);
		
		t.left.parent = t;
		t.right.parent = t;
		
		return t;
	}
	
	public static void main(String args[])
	{
		String input_dir = "/home2bak/plai2/datasets/limestone/bucket_scaled/256/";
		String filename = "scan1_buckets_scaled_256.txt";
		
		ArrayList<PointND> points = PointCloudReader.ReadFile(input_dir+filename); // read all the points
		ArrayList<GeoVertex> vertices = new ArrayList<GeoVertex>(points.size());
		
		for (PointND pt: points) vertices.add(new GeoVertex(pt.get_coord(0), pt.get_coord(1), pt.get_coord(2)));
		
		
		KDTree tree = new KDTree(vertices);
		
	}

}
